package com.cube.algorithms.heuristic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;


/**
 * @author litb
 * @since 2025/6/18 15:48
 * <p>
 * 使用模拟退火（Simulated Annealing）启发式算法解决旅行商问题(TSP)的示例。
 */
public class TspSimulatedAnnealingExample {

    /**
     * 程序主入口，用于演示算法效果。
     *
     * @param args 命令行参数（未使用）
     */
    public static void main(String[] args) {
        // 创建一个城市列表用于测试
        List<City> cities = new ArrayList<>();
        cities.add(new City("北京", 116.46, 39.92));
        cities.add(new City("上海", 121.48, 31.22));
        cities.add(new City("广州", 113.23, 23.16));
        cities.add(new City("深圳", 114.07, 22.62));
        cities.add(new City("成都", 104.06, 30.67));
        cities.add(new City("杭州", 120.19, 30.26));
        cities.add(new City("西安", 108.95, 34.27));
        cities.add(new City("武汉", 114.31, 30.52));

        // 创建算法实例并执行
        TspSimulatedAnnealingExample solver = new TspSimulatedAnnealingExample();
        // 设置模拟退火参数：初始温度，冷却率，最低温度
        Tour resultTour = solver.findTour(cities, 10000, 0.999, 1);

        // 打印结果
        System.out.println("模拟退火算法找到的路径:");
        String pathString = resultTour.getPath().stream()
                .map(City::getName)
                .collect(Collectors.joining(" -> "));
        System.out.println(pathString);
        System.out.printf("总距离: %.2f%n", resultTour.getTotalDistance());

        System.out.println("\n注意: 此解是启发式算法给出的近似最优解。每次运行结果可能因随机性而不同。");
    }

    /**
     * 核心方法：使用模拟退火算法寻找最优路径。
     *
     * @param cities         城市列表
     * @param temperature    初始温度。一个较高的值，用于在初期有更大概率探索"坏"的解。
     * @param coolingRate    冷却系数。每次迭代后温度降低的比率，通常是一个接近1的数（如0.995）。
     * @param minTemperature 终止温度。当温度低于此值时，算法停止。
     * @return 最终找到的最优路径（Tour对象）
     */
    public Tour findTour(List<City> cities, double temperature, double coolingRate, double minTemperature) {
        // 创建一个初始解：随机打乱城市顺序
        List<City> currentSolution = new ArrayList<>(cities);
        Collections.shuffle(currentSolution);

        // 初始化最优解为当前解
        List<City> bestSolution = new ArrayList<>(currentSolution);
        double bestDistance = calculateTotalDistance(bestSolution);

        // 当系统"温度"高于最低温度时，持续进行退火过程
        while (temperature > minTemperature) {
            // 产生一个新的邻近解
            List<City> newSolution = generateNeighbor(new ArrayList<>(currentSolution));

            // 计算当前解和新解的"能量"（即总距离）
            double currentEnergy = calculateTotalDistance(currentSolution);
            double newEnergy = calculateTotalDistance(newSolution);

            // 计算能量差，决定是否接受新解
            // acceptanceProbability方法决定了是否要移动到新解
            if (acceptanceProbability(currentEnergy, newEnergy, temperature) > Math.random()) {
                currentSolution = newSolution;
            }

            // 如果当前解优于已知的最优解，则更新最优解
            if (calculateTotalDistance(currentSolution) < bestDistance) {
                bestSolution = new ArrayList<>(currentSolution);
                bestDistance = calculateTotalDistance(bestSolution);
            }

            // 降低温度，为下一次迭代做准备
            temperature *= coolingRate;
        }

        return new Tour(bestSolution, bestDistance);
    }

    /**
     * 计算一个路径的总距离。
     *
     * @param tour 城市路径列表
     * @return 总距离
     */
    private double calculateTotalDistance(List<City> tour) {
        double totalDistance = 0.0;
        for (int i = 0; i < tour.size() - 1; i++) {
            totalDistance += tour.get(i).distanceTo(tour.get(i + 1));
        }
        // 不要忘记加上从最后一个城市回到起点的距离
        if (!tour.isEmpty()) {
            totalDistance += tour.get(tour.size() - 1).distanceTo(tour.get(0));
        }
        return totalDistance;
    }

    /**
     * 产生一个邻近解。
     * 这里采用简单的"2-opt"思想的变体：随机交换路径中两个城市的位置。
     *
     * @param tour 当前路径
     * @return 一个新的路径
     */
    private List<City> generateNeighbor(List<City> tour) {
        if (tour.size() < 2) {
            return tour;
        }
        // 随机选择两个不同的位置
        int pos1 = (int) (tour.size() * Math.random());
        int pos2 = (int) (tour.size() * Math.random());
        while (pos1 == pos2) {
            pos2 = (int) (tour.size() * Math.random());
        }

        // 交换这两个位置的城市
        Collections.swap(tour, pos1, pos2);
        return tour;
    }

    /**
     * 计算接受新解的概率。
     * 这是模拟退火算法的核心。
     *
     * @param currentEnergy 当前解的能量（距离）
     * @param newEnergy     新解的能量（距离）
     * @param temperature   当前温度
     * @return 接受新解的概率（0到1之间）
     */
    private double acceptanceProbability(double currentEnergy, double newEnergy, double temperature) {
        // 如果新解更好（能量更低），则百分之百接受
        if (newEnergy < currentEnergy) {
            return 1.0;
        }
        // 如果新解更差，则根据Metropolis准则计算一个接受概率
        // 这个概率随着温度的降低和能量差的增大而减小
        return Math.exp((currentEnergy - newEnergy) / temperature);
    }

    /**
     * 内部类，用于表示一个城市。
     * 从TspHeuristicExample中复用，保持一致性。
     */
    public static class City {
        private final String name;
        private final double x;
        private final double y;

        public City(String name, double x, double y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }

        public String getName() {
            return name;
        }

        public double distanceTo(City other) {
            double deltaX = this.x - other.x;
            double deltaY = this.y - other.y;
            return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
        }

        @Override
        public String toString() {
            return name;
        }
    }

    /**
     * 用于封装TSP问题解的内部类。
     * 包含路径和总距离。
     */
    public static class Tour {
        private final List<City> path;
        private final double totalDistance;

        public Tour(List<City> path, double totalDistance) {
            // 为了显示闭环，将起点添加到路径末尾
            List<City> finalPath = new ArrayList<>(path);
            if (!finalPath.isEmpty()) {
                finalPath.add(finalPath.get(0));
            }
            this.path = finalPath;
            this.totalDistance = totalDistance;
        }

        public List<City> getPath() {
            return path;
        }

        public double getTotalDistance() {
            return totalDistance;
        }
    }
} 